// 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
// 说明：每次只能向下或者向右移动一步。

function minPathSum(grid: number[][]): number {
  // 输入校验
  if (grid.length < 1) {
    return 0;
  }
  let rows: number = grid.length;// 取得行
  let cols: number = grid[0].length;// 取得列
  let dp: number[][] = grid;// 利用原矩阵充当DP矩阵即可
  // 计算一行、一列的dp矩阵值
  for (let i = 1; i < cols; i++) {
    dp[0][i] += dp[0][i - 1];
  }
  for (let i = 1; i < rows; i++) {
    dp[i][0] += dp[i - 1][0];
  }
  // 状态转移方程
  for (let i = 1; i < rows; i++) {
    for (let j = 1; j < cols; j++) {
      dp[i][j] += Math.min(dp[i - 1][j], dp[i][j - 1]);
    }
  }
  return dp[rows - 1][cols - 1];
}

// 这道题目也是一道比较经典的动态规划的算法题目
// 题目要求只能向右或向下走，换句话说只需要考虑矩阵左边界和上边界。
// 这里采用DP矩阵，DP矩阵直接在原矩阵基础上修改即可
// 首先我们需要考虑的是边界，因为边界可能缺失上格或左格，可能产生数组访问越界的情况
// 通过循环累加即可求出第一行第一列的Dp矩阵值
// 然后进行剩余DP矩阵值的求解，这里就要用到状态转移方程
// 这里的话就是比较直观，我们需要先求解出左格子、上格子中的最小值，然后在DP矩阵上直接拿到最小值累加即可
// 然后逐次用结果填满DP矩阵，最后的结果值即为DP矩阵的右下角，返回即可。

